package exercises.leetcode;

import java.util.List;

/**
 * <a href="https://leetcode-cn.com/problems/triangle/">
 * 120. 三角形最小路径和</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给定一个三角形 triangle ，找出自顶向下的最小路径和。
 * <p>
 * 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
 * <p>
 * 示例 1：
 * <p>
 * 输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
 * 输出：11
 * 解释：如下面简图所示：<pre>{@code
 *    2
 *   3 4
 *  6 5 7
 * 4 1 8 3}</pre>
 * 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
 * 示例 2：
 * <p>
 * 输入：triangle = [[-10]]
 * 输出：-10
 *  
 * <p>
 * 提示：
 * <ol>
 * <li>1 <= triangle.length <= 200</li>
 * <li>triangle[0].length == 1</li>
 * <li>triangle[i].length == triangle[i - 1].length + 1</li>
 * <li>-104 <= triangle[i][j] <= 104</li>
 * </ol>
 * 进阶：
 * <p>
 * 你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？
 *
 * @author or2
 * @date 2021年09月30日 时间: 10:05
 */
public class No120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        int floors = triangle.size();
        List<Integer> layer = triangle.get(floors - 1);
        for (int i = floors - 1; i > 0; i--) {
            List<Integer> upperStory = triangle.get(i - 1);
            for (int j = 0, arrLen = layer.size(); j < arrLen - 1; j++)
                upperStory.set(j, Math.min(layer.get(j), layer.get(j + 1)) + upperStory.get(j));
            layer = upperStory;
        }

        return triangle.get(0).get(0);
    }

    public int custom(List<List<Integer>> triangle) {
        int floors = triangle.size();
        Integer[] layer = triangle.get(floors - 1).toArray(Integer[]::new);
        for (int i = floors - 1; i > 0; i--) {
            Integer[] upperStory = triangle.get(i - 1).toArray(Integer[]::new);
            for (int j = 0, arrLen = layer.length; j < arrLen - 1; j++)
                upperStory[j] = Math.min(layer[j], layer[j + 1]) + upperStory[j];
            layer = upperStory;
        }

        triangle = null;
        System.gc();
        try {
            Thread.sleep(997);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        return layer[0];
    }

    public int customV2(List<List<Integer>> triangle) {
        int floors = triangle.size();
        if (floors == 1)
            return triangle.get(0).get(0);

        int[] dp = new int[floors];
        List<Integer> last = triangle.get(floors - 1);
        for (int i = 0; i < last.size(); i++) dp[i] = last.get(i);

        for (int i = floors - 1; i > 0; i--) {
            List<Integer> upperStory = triangle.get(i - 1);
            for (int j = 0; j < i; j++)
                dp[j] = Math.min(dp[j], dp[j + 1]) + upperStory.get(j);
        }

        return dp[0];
    }

    public int superQuick(List<List<Integer>> triangle) {
        int rows = triangle.size();
        int ans = Integer.MAX_VALUE;
        int[] lastLayer = layerDistance(triangle, rows - 1);
        for (int i = 0; i < rows; i++) {
            ans = Math.min(ans, lastLayer[i]);
        }
        return ans;
    }

    public int[] layerDistance(List<List<Integer>> triangle, int n) {
        if (n == 0) return (new int[]{triangle.get(0).get(0)});
        List<Integer> currentLayer = triangle.get(n);

        int[] prevLayerDistance = layerDistance(triangle, n - 1);

        int[] currentLayerDistance = new int[n + 1];
        currentLayerDistance[0] = prevLayerDistance[0] + currentLayer.get(0);
        for (int i = 1; i < n; i++)
            currentLayerDistance[i] = Math.min(prevLayerDistance[i - 1], prevLayerDistance[i]) + currentLayer.get(i);

        currentLayerDistance[n] = prevLayerDistance[n - 1] + currentLayer.get(n);
        return currentLayerDistance;
    }
}
